/*
 * Copyright (C) 2010 Jens Bierschenk
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.googlecode.algorithmlaboratory.binarytree;

import java.util.Collection;

import com.googlecode.algorithmlaboratory.AbstractTree;

public class BinaryTree<E extends Comparable<E>> extends AbstractTree<E> {
	
	/**
	 * Constructs a new, empty set, sorted according to the elements natural order.
	 */
	public BinaryTree() {
		super();
	}
	
	/**
	 * Constructs a new, insert with the elements of the collection, sorted according to the elements natural order.
	 * @param collection of elements, that should be insert
	 */
	public BinaryTree(Collection<E> collection) {
		super(collection);
	}

	/**
	 * Adds the specified element to this binary tree if it is not already present. If this set already contains the element, 
	 * the call leaves the set unchanged and returns false.
	 * @param value element to be added to this set
	 * @return {@code true} if this set did not already contain the specified element 
	 * @throws NullPointerException - if the specified element is null
	 */
	@Override public boolean add(E value) {
		if(value == null){
			throw new NullPointerException( "The specified parameter is null." );
		
		}else if(root == null){
			root = new BinaryTreeNode<E>(null, value);
		}else{
			BinaryTreeNode<E> parent = null;
			BinaryTreeNode<E> child = (BinaryTreeNode<E>) root;
			
			while(child != null){
				int cmp = child.getValue().compareTo(value);
				if(cmp == 0){
					return false;
				}else{
					parent = child;
					child = (BinaryTreeNode<E>) (cmp > 0 ? child.getLeftNode() : child.getRightNode());
				}
			}
			BinaryTreeNode<E> node = new BinaryTreeNode<E>(parent, value);
			if(parent.getValue().compareTo(value) > 0){
				parent.setLeftNode(node);
			}else{
				parent.setRightNode(node);
			}
		}
		size++;
		return true;
	}

	/**
	 * Removes the specified element from this binary tree if it is present. Returns {@code true} if the specified element removed.
	 * @param object to be removed from this binary tree, if present
	 * @return {@code true} if the specified element removed
	 * @return {@code false} if the specified element not removed
	 * @throws NullPointerException if the specified element is null
	 * @throws ClassCastException if the specified object cannot be compared with the elements currently in the binary tree
	 */
	@SuppressWarnings("unchecked")
	@Override public boolean remove(Object object) {
		BinaryTreeNode<E> x = null;
		BinaryTreeNode<E> y = null;
		
		BinaryTreeNode<E> baseNode = (BinaryTreeNode<E>) findNode((E) object);
		if(baseNode != null){
			if(baseNode.getLeftNode() == null || baseNode.getRightNode() == null){
				y = baseNode;
			}else{
				y = (BinaryTreeNode<E>) successor(baseNode);
			}
			if(y.getLeftNode() != null){
				x = (BinaryTreeNode<E>) y.getLeftNode();
			}else{
				x = (BinaryTreeNode<E>) y.getRightNode();
			}
			if(x != null){
				x.setParentNode(y.getParentNode());
			}
			if(y.getParentNode() == null){
				root = x;
			}else if(y == y.getParentNode().getLeftNode()){
				y.getParentNode().setLeftNode(x); 
			}else{
				y.getParentNode().setRightNode(x);
			}
			if(y != baseNode){
				baseNode.setValue(y.getValue());
			}
			size--;
			return true;
		}else{
			return false;
		}
	}
}
